When an adder is formed, the most important factor related to the efforts to increase the operation speed is the delay in propagation of the carry signal. For example, in a ripple carry type adder, because the carry signal is propagated sequentially from the least significant position to the most significant position, a delay time is generated proportional to the bit length of the addition object signal until the operation result and overflow of the most significant position are determined.
FIG. 16A is a circuit diagram illustrating an example of constitution of a ripple carry type adder that adds 4-bit signals. The ripple carry type adder shown in FIG. 16A is composed of four full adders (1)-(4).
Full adders (1)-(4) take 1-bit carry signal C1 of from the lower position as input, and at the same time, have 1-bit signals a and b as addition objects as inputs. Then, each of the full adders outputs 1-bit signal s as the addition result, and at the same time, outputs 1-bit carry signal c0 to the upper position. Addition result signal s and carry signal c0 are expressed by the following equations, respectively.
[Numerical Formula 1]s=a⊕b⊕c1  (1)c0=a·b+(a⊕b)·c1  (2)
The signals of the various positions of the addition object signals are input to full adders (1)-(4) shown in FIG. 16B. That is, in a corresponding order, the least significant position (a0, b0), . . . , and finally, the most significant position (a3, b3) are input to full adders (1), . . . , (4), respectively. Also, for each of full adders (1)-(4), the carry signal is input from the lower-position full adder. That is, carry signal cin from the exterior is input to full adder (1). Carry signal c0 from full adder (1) is input to full adder (2). Carry signal c1 from full adder (2) is input to full adder (3). Carry signal c2 from full adder (3) is input to full adder (4). Signals s0-s3 as addition results output from full adders (1)-(4) correspond to the least significant position-most significant position of the 4-bit addition results. The carry signal output from full adder (4) shows overflow in the 4-bit addition result.
In the adder with the constitution shown in FIG. 16A, before output of lower-position carry signal c2, the addition result s3 of the most significant position and its overflow signal c3 are not determined. Also, the carry signal c2 is not determined until output of the lower-position carry signal c1, and carry signal c1 is not determined until output of the lower-position carry signal c0.
That is, in order to determine the addition result and carry for a certain position, it is necessary to determine the carry signals of all the positions lower than the position. Consequently, the propagation path of the carry signal (indicated by broken line in FIG. 16A) becomes the longest delay path (critical path) in the ripple type adder. As the bit length of the addition object signals increases, the number of stages of full adders that have to be added increases. All these added full adders are added to the critical path. Consequently, the delay time before the final addition result can be determined increases.
As a method for alleviating the delay in propagation of the carry signal, a scheme has been proposed in which a carry look-ahead circuit is used. In this scheme, the least significant position of the addition object signal is taken as the first position, and carry signal ci formed due to addition of the (i+1)th position (where, i is a positive integer including zero) has the following relationship, which is exploited to detect the carry of the upper position without waiting for detection of the lower-position carry.
[Numerical Formula 2]
                                                                        c                i                            =                            ⁢                                                                                          p                      ′                                        i                                    ⁢                                      c                                          i                      -                      1                                                                      +                                  g                  i                                                                                                        =                            ⁢                                                                                          p                      ′                                        i                                    ⁢                                                            p                      ′                                                              i                      -                      1                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        1                                    ⁢                                      g                    o                                                  +                                                                                                      ⁢                                                                                          p                      ′                                        i                                    ⁢                                                            p                      ′                                                              i                      -                      1                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        2                                    ⁢                                      g                    1                                                  +                                                                                                      ⁢              ⋮                                                                                        ⁢                                                                                          p                      ′                                        i                                    ⁢                                      g                                          i                      -                      1                                                                      +                                                                                                      ⁢                              g                i                                                                        (        3        )            
In Equation (3), using signals (ai, bi) of the (i+1)th position of the addition object signals, signals pi and gi can be expressed by the following equations.
[Numerical Formula 3]pi=ai⊕bi  (4)gi=ai·bi  (5)
Usually, signal pi is known as a carry propagation signal, and signal gi is known as a carry generation signal. Also, in Equation (3), carry signal c−1 is set at “0”, that is, it is assumed that no carry input exists from the exterior with respect to the first position of the addition object signals. On the other hand, when external carry signal cin exists, carry signal ci is expressed by the following equation.
[Numerical Formula 4]
                                                                                          c                  i                                =                                ⁢                                                                                                    p                        ′                                            i                                        ⁢                                                                  p                        ′                                                                    i                        -                        1                                                              ⁢                                                                                  ⁢                                                                  ⋯                        ⁢                                                                                                                      ′                                        ⁢                                                                  p                        ′                                            o                                        ⁢                                          c                                              i                        ⁢                                                                                                  ⁢                        n                                                                              +                                            ⁢                                                                                                                                    ⁢                                                                                          p                      ′                                        i                                    ⁢                                                            p                      ′                                                              i                      -                      1                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        1                                    ⁢                                      g                    0                                                  +                            ⁢                                                                                                                                    ⁢                                                                                          p                      ′                                        i                                    ⁢                                                            p                      ′                                                              i                      -                      1                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        2                                    ⁢                                      g                    1                                                  +                            ⁢                                                                                                                                    ⁢              ⋮                                                                                        ⁢                                                                                          p                      ′                                        i                                    ⁢                                      g                                          i                      -                      1                                                                      +                                                                                                      ⁢                              g                i                                                                        (                  3          ⁢          A                )            
For example, if no external carry signal cin exists, by means of Equation (3) carry signal c3 from the most significant position (4th position) in the 4-bit adder can be expressed by the following equation.
[Numerical Formula 5]
                                                        c3              =                            ⁢                                                p3                  ·                  p2                  ·                  p1                  ·                  g0                                +                                                                                                      ⁢                                                p3                  ·                  p2                  ·                  g1                                +                                                                                                      ⁢                                                p3                  ·                  g2                                +                                                                                                      ⁢              g3                                                          (        6        )            
FIG. 17A is a circuit diagram illustrating an example of the generation circuit of carry signal c3 formed according to the relationship of Equation (6). The generation circuit of carry signal c3 shown in FIG. 17A has half adders (5)-(8), each of which is shown in FIG. 17B, 4-input NAND gates (9) and (13), 3-input NAND gate (10), 2-input NAND gate (11), and inverter (12). Half adders (5)-(8) take the addition object signals of the various positions as inputs, perform exclusive OR expressed by Equation (4) and AND expressed by Equation (5), and output a carry propagation signal and carry generation signal. That is, corresponding to the order, half adders (5), . . . , (8) have the least significant position (a0, b0), . . . , and most significant position (a3, b3) of the addition object 4-bit signals as inputs, respectively. Then, for the input addition object signals, exclusive OR and AND are performed, and then carry propagation signal/carry generation signal groups (p0, g0), . . . , (p3, g3) are output, respectively.
The 4-input NAND gate (9) takes carry generation signal g0 from half adder (5) and carry propagation signals p1-p3 output from half adders (6)-(8) as inputs, and outputs NAND of the four input signals. This output signal corresponds to the NOT signal of the first item on the right side of Equation (6). The 3-input NAND gate (10) takes carry generation signal g1 from half adder (6) and carry propagation signals p2 and p3 output from half adders (7) and (8) as inputs, and outputs NAND of the three input signals. This output signal corresponds to the NOT signal of the second item on the right side of Equation (6). The 2-input NAND gate (11) takes carry generation signal g2 from half adder (7) and carry propagation signal p3 output from half adder (8) as inputs, and outputs NAND of the two input signals. This output signal corresponds to the NOT signal of the third item on the right side of Equation (6). Inverter (12) outputs NOT of carry generation signal g3 output from half adder (8). This output signal corresponds to the signal of NOT of the fourth item on the right side of Equation (6). The 4-input NAND gate (13) takes the output signals of NAND gates (9)-(11) and inverter (12) as its inputs, and outputs NAND of the input four signals. This output signal corresponds to carry signal c3 shown in Equation (6).
With the aid of the generation circuit of carry signal c3 with the constitution, carry signal c3 can be formed directly from addition object signals (a0, . . . , a3) and (b0, . . . , b3), without waiting for determination of the lower-position carry signals (c0-c2). Compared with the ripple carry system shown in FIG. 16A, the delay in propagation of the carry signal can be shortened. The circuit shown in FIG. 17A is a circuit for forming the carry signal for the 4th position counted from the least significant position. When a carry signal is to be formed for addition of more bits, one usually adopts a system in which plural CLA circuits are connected in a hierarchical constitution.
FIG. 18 is a circuit diagram illustrating an example of the generation circuit of carry signal c15 composed of plural CLA circuits connected in a hierarchical constitution. The generation circuit of carry signal c15 shown in FIG. 18 has 4-bit half adders (21)-(24) and CLA circuits (25)-(29). 4-bit half adders (21)-(24) have the 4-bit signals obtained by dividing the 16-bit addition object signals into four portions as inputs, and they operate using Equations (4) and (5) to get a carry propagation signal and carry generation signal respectively, for the various positions. That is, half adder (21) has the addition object signals (a0, . . . , a3) and (b0, . . . , b3) of the least significant position (first position)-fourth position as inputs. Half adder (22) has the addition object signals (a4, . . . , a7) and (b4, . . . , b7) of the fifth-eighth positions as inputs. Half adder (23) has the addition object signals (a8, . . . , a11) and (b8, . . . , b11) of the ninth-12th positions as inputs. Half adder (24) has the addition object signals (a12, . . . , a15) and (b12, . . . , b15) of the 13th-16th positions as inputs.
For each position of the input addition object signals, exclusive OR according to Equation (4) and AND according to Equation (5) are determined in operation. Half adder (21) calculates and outputs carry propagation signal (p0, . . . , p3) and carry generation signal (g0, . . . , g3). Half adder (22) calculates and outputs carry propagation signal (p4, . . . , p7) and carry generation signal (g4, . . . , g7). Half adder (23) calculates and outputs carry propagation signal (p8, . . . , p11) and carry generation signal (g8, . . . , g11). Half adder (24) calculates and outputs carry propagation signal (p12, . . . p15) and carry generation signal (g12, . . . , g15).
FIG. 19 is a circuit diagram illustrating an example of constitution of 4-bit half adder (21). For example, as shown in FIG. 19, the 4-bit half adder (21) is composed of four half adders (30)-(33) of 1-bit half adders. Also, other 4-bit half adders (22)-(24) may have the same constitution as that shown in FIG. 19. CLA circuits (25)-(28) have carry propagation 4-bit signals and carry generation 4-bit signals output from 4-bit half adders (21)-(24) as inputs, respectively, and, corresponding to these signals, they output carry propagation 1-bit signals and carry generation 1-bit signals, respectively.
That is, CLA circuit (25) has carry propagation signal (p0, . . . , p3) and carry generation signal (g0, . . . , g3) of half adder (21) input to it. CLA circuit (26) has carry propagation signal (p4, . . . , p7) and carry generation signal (g4, . . . , g7) of half adder (22) input to it. CLA circuit (27) has carry propagation signal (p8, . . . , p11) and carry generation signal (g8, . . . , g11) of half adder (23) input to it. CLA circuit (28) has carry propagation signal (p12, . . . , p15) and carry generation signal (g12, . . . , g15) of half adder (24) input to it. Then, corresponding to the inputs, carry propagation 1-bit signals and carry generation 1-bit signals are calculated. That is, CLA circuit (25) calculates and outputs carry propagation signal P0 and carry generation signal G0. CLA circuit (26) calculates and outputs carry propagation signal P1 and carry generation signal G1. CLA circuit (27) calculates and outputs carry propagation signal P2 and carry generation signal G2. CLA circuit (28) calculates and outputs carry propagation signal P3 and carry generation signal G3. The input carry propagation 4-bit signals for CLA circuits (25)-(28) are represented as signals p(0)-p(3) from the lower position, also, the input carry generation 4-bit signals are represented as signals g(0)-g(3). In this case, output 1-bit carry propagation signal P and output 1-bit carry generation signal G are expressed by the following equations.
[Numerical Formula]
                                                        G              =                            ⁢                                                                                          p                      ′                                                              (                      3                      )                                                        ⁢                                                            p                      ′                                                              (                      2                      )                                                        ⁢                                                            p                      ′                                                              (                      1                      )                                                        ⁢                                      g                                          (                      0                      )                                                                      +                                                                                                      ⁢                                                                                          p                      ′                                                              (                      3                      )                                                        ⁢                                                            p                      ′                                                              (                      2                      )                                                        ⁢                                      g                                          (                      1                      )                                                                      +                                                                                                      ⁢                                                                                          p                      ′                                                              (                      3                      )                                                        ⁢                                      g                                          (                      2                      )                                                                      +                                                                                                      ⁢                              g                                  (                  3                  )                                                                                        (        7        )                                P        =                                            p              ′                                      (              3              )                                ⁢                                    p              ′                                      (              2              )                                ⁢                                    p              ′                                      (              1              )                                ⁢                      p                          (              0              )                                                          (        8        )            
FIG. 20 is a circuit diagram illustrating an example of the constitution of CLA circuit (25). Circuits (14)-(18) generating output carry generation signal G0 in CLA circuit (25) are identical to circuits (9)-(13) generating carry signal c3 shown in FIG. 17. Also, generation of carry propagation signal P0 is realized by performing operation of NAND for carry propagation signals p0-p3 in 4-input NAND gate (19), followed by NOT of the operation result with inverter (20). Other CLA circuits (25)-(28) may also have the same circuit constitution as that shown in FIG. 20. CLA circuit (29) takes output 4-bit carry propagation signal (P0, . . . , P3) and output 4-bit carry generation signal (G0, . . . , G3) from CLA circuits (26)-(28) as inputs, and corresponding to them, it outputs 1-bit carry propagation signal Po and 1-bit carry generation signal Go. For CLA circuit (29), output carry generation signal Go and output carry propagation signal Po are calculated in the same way as in CLA circuits (25)-(28) by just replacing input carry propagation signal (p(0), . . . , p(3)) and input carry generation signal (g(0), . . . , g(3)) with output carry propagation signal (P0, . . . , P3) and output carry generation signal (G0, . . . , G3) of CLA circuits (25)-(28) in Equations (7) and (8). Consequently, the circuit constitution of CLA circuit (29) can be realized in the same way as in FIG. 20.
In the generation circuit of carry signal c15 with the constitution, when i=15 in the Equation (3), output carry generation signal Go of CLA circuit (29) is equal to carry signal c15. That is, using Equation (3), carry signal c15 is expressed by the following equation.
[Numerical Formula 7]
                                                                        C                15                            =                            ⁢                                                                                          p                      ′                                        15                                    ⁢                                                            p                      ′                                        14                                    ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        1                                    ⁢                                      g                    o                                                  +                                                                                                      ⁢                                                                                          p                      ′                                        15                                    ⁢                                                            p                      ′                                        14                                    ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                        2                                    ⁢                                      g                    1                                                  +                                                                                                      ⁢                                                                                          p                      ′                                        15                                    ⁢                                      g                    14                                                  +                                                                                                      ⁢                              g                15                                                                        (        9        )            
Output carry propagation signals P1-P3 of CLA circuits (26)-(28) and output carry generation signal G0 of CLA circuit (25) are expressed by the following equations.
[Numerical Formula 8]
                              P          3                =                              p            15                    ·                      p            14                    ·                      p            13                    ·                      p            12                                              (                  10          ⁢          A                )                                          P          2                =                              p            11                    ·                      p            10                    ·                      p            9                    ·                      p            8                                              (                  10          ⁢          B                )                                          P          1                =                              p            7                    ·                      p            6                    ·                      p            5                    ·                      p            4                                              (                  10          ⁢          C                )                                                                                    G                0                            =                            ⁢                                                                    p                    3                                    ·                                      p                    2                                    ·                                      p                    1                                    ·                                      g                    0                                                  +                                                                                                      ⁢                                                                    p                    3                                    ·                                      p                    2                                    ·                                      g                    1                                                  +                                                                                                      ⁢                                                                    p                    3                                    ·                                      g                    2                                                  +                                                                                                      ⁢                              g                3                                                                        (                  10          ⁢          D                )            
By substituting Equations (10A)-(10D) into items 1-4 on the right side of Equation (9), one can represent OR W14 of items 1-4 by the following equation.
[Numerical Formula 9]
                                                                        W                14                            =                            ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      P                    1                                    ·                                      p                    3                                    ·                                      p                    2                                    ·                                      p                    1                                    ·                                      g                    0                                                  +                                                                                                      ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      P                    1                                    ·                                      p                    3                                    ·                                      p                    2                                    ·                                      g                    1                                                  +                                                                                                      ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      P                    1                                    ·                                      p                    3                                    ·                                      g                    2                                                  +                                                                                                      ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      P                    1                                    ·                                      g                    3                                                  +                                                                                        =                            ⁢                                                P                  3                                ·                                  P                  2                                ·                                  P                  1                                ·                                  G                  0                                                                                        (        11        )            
OR of items 5-8, items 9-12, and items 13-16 on the right side of Equation (9), just as OR W14 of Equation (11), may also be represented with the output carry propagation signals and output carry generation signals of CLA circuits (25)-(28). As a result, carry signal c15 is expressed by the following equation.
[Numerical Formula 10]
                                                                        C                15                            =                            ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      P                    1                                    ·                                      G                    o                                                  +                                                                                                      ⁢                                                                    P                    3                                    ·                                      P                    2                                    ·                                      G                    1                                                  +                                                                                                      ⁢                                                                    P                    3                                    ·                                      G                    2                                                  +                                                                                                      ⁢                              G                3                                                                        (                  9          ⁢          A                )            
The right side of Equation (9A) is equal to output carry generation signal Go of CLA circuit (29). From this fact, one can see that output carry generation signal Go becomes equal to carry signal c15. The circuit shown in FIG. 18 is a CLA circuit that takes a 4-bit carry propagation signal and a 4-bit carry generation signal as inputs, and outputs a carry propagation 1-bit signal and carry generation 1-bit signal. Usually, for a CLA circuit that takes an N-bit carry propagation signal and an N-bit carry generation signal, output carry propagation signal P and output carry generation signal G are expressed by the following equation.
[Numerical Formula 11]
                                                        G              =                            ⁢                                                                                          p                      ′                                                              (                                              N                        -                        1                                            )                                                        ⁢                                                            p                      ′                                                              (                                              N                        -                        2                                            )                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                                              (                      1                      )                                                        ⁢                                      g                                          (                      0                      )                                                                      +                                                                                                      ⁢                                                                                          p                      ′                                                              (                                              N                        -                        1                                            )                                                        ⁢                                                            p                      ′                                                              (                                              N                        -                        2                                            )                                                        ⁢                                                                          ⁢                                                            ⋯                      ⁢                                                                                                            ′                                    ⁢                                                            p                      ′                                                              (                      2                      )                                                        ⁢                                      g                                          (                      1                      )                                                                      +                                                                                                      ⁢              ⋮                                                                                        ⁢                                                                                          p                      ′                                                              (                                              N                        -                        1                                            )                                                        ⁢                                      g                                          (                                              N                        -                        1                                            )                                                                      +                                                                                                      ⁢                              g                                  (                                      N                    -                    1                                    )                                                                                        (        12        )                                P        =                                            p              ′                                      (                              N                -                1                            )                                ⁢                                    p              ′                                      (                              N                -                2                            )                                ⁢                                          ⁢          ⋯          ⁢                                          ⁢                                    p              ′                                      (              1              )                                ⁢                      p                          (              0              )                                                          (        13        )            
For example, for a carry look-ahead circuit made of plural CLA circuits connected in hierarchical constitution, the technology described in Patent Reference 1 is available.
For the CLA circuit used in the generation circuit of a carry signal shown in FIGS. 17 and 18, NANDs having plural inputs, such as 3 inputs and 4 inputs, are used. Usually, in a NAND gate, NOR gate, and other gates, the larger the input signal number, the larger the number of series stages of transistors inserted between the output terminal and the power source line or the ground line. For example, for a 4-input NAND gate, 4 stages of transistors are inserted in series between the output terminal and the ground line. Consequently, for a gate having plural inputs, the driving ability of the output current decreases, and the operation speed tends to decrease.
In order to suppress decrease in the speed of a multi-input gate, it is necessary to increase the size or gate width of the transistors so as to decrease the ON resistance. As a result, the circuit size increases, and due to an increase in gate capacitance, the driving loss of transistors increases. This is undesirable. However, because the generation circuit of the carry signal is the critical path of the entire adder, in order to improve the overall performance of the adder, it is necessary to increase the area of the transistors used in the plural input gates of the CLA circuit. Consequently, in a conventional CLA circuit, as a cost in increasing the operation speed of the adder, the circuit size and power consumption increase, and this is always a problem.
FIG. 5 in Japanese Kokai Patent Application No. Hei 5[1993]-61643 is a circuit diagram illustrating an example in which composite gates are used in a CLA circuit that generates the same signal as that of output carry generation signal G expressed by Equation (7). FIG. 21 is a circuit diagram illustrating an example of a CLA circuit made of the composite gates. For the composite gate shown in FIG. 21, four transistors, that is, p-type MOS transistors Qp1-Qp4, are inserted in series between the input terminal of inverter (34) and power source line Vcc, and four transistors, that is, n-type MOS transistors Qn1-Qn4, are inserted in series between the input terminal of inverter (34) and ground line G. Consequently, in order to increase the speed of the CLA circuit, it is necessary to increase the size of these transistors, and as explained above, problems of increase in circuit size and power consumption occur. This is undesirable.